#include <iostream>
#include <cstdio>
#include <cstdlib>

typedef struct Node {
    int val;
    int ltag, rtag;
    struct Node *lchild, *rchild;
} Node;

Node *getNewNode(int val) {
    Node *p = (Node *)malloc(sizeof(Node));
    p->val = val;
    p->ltag = p->rtag = 0;
    p->lchild = p->rchild = nullptr;
    return p;
}

Node *insert(Node *root, int val) {
    if(root == nullptr) return getNewNode(val);
    if(root->val == val) return root;
    if(root->val > val) root->lchild = insert(root->lchild, val);
    else root->rchild = insert(root->rchild, val);
    return root;
}

void backOrder(Node *root) {
    if(root == nullptr) return ;
    if(root->ltag == 0) backOrder(root->lchild);
    if(root->rtag == 0) backOrder(root->rchild);
    printf("%d-> ", root->val);
    return ;
}

void preFace(Node *root) {
    if(root == nullptr) return ;
    printf("%d(", root->val);
    if(root->ltag == 0) preFace(root->lchild);
    printf(",");
    if(root->rtag == 0) preFace(root->rchild);
    printf(")");
    return ;
}

void buildThread(Node *root) {
    if(root == nullptr) return ;
    static Node *pre = nullptr;
    buildThread(root->lchild);
    buildThread(root->rchild);
    if(root->ltag == 0) {
        root->lchild = pre;
        root->ltag = 1;
    }
    if(pre && pre->rtag == 0) {
        pre->rchild = root;
        pre->rtag = 1;
    }
    pre = root;
    return ;
}

Node *mostleft(Node *root) {
    while(root && root->ltag == 1 && root->lchild) {
        root = root->lchild;
    }
    return root;
}

void outPut(Node *root) {
    if(root == nullptr) return ;
    Node *p = mostleft(root);
    while(p) {
        printf("%d ", p->val);
        if(p->rtag == 1) p = p->rchild;
        else if(p->rtag == 0) break;
    }
    return ;
}

void clearNode(Node *root) {
    if(root == nullptr) return ;
    if(root->ltag == 0) clearNode(root->lchild);
    if(root->rtag == 0) clearNode(root->rchild);
    free(root);
    return ;
}

#define MAX_N 10
int main() {
    Node *root = nullptr;
    for(int i = 0; i < MAX_N; i++) {
        root = insert(root, rand() % 100);
    }
    backOrder(root);
    printf("\n\n");
    preFace(root);
    printf("\n\n");
    buildThread(root);
    outPut(root);
    printf("\n\n");
    clearNode(root);
    return 0;
}